The present invention relates to a circuit for estimating an unknown system using an adaptive filter and, more particularly, to an adaptive filter suitably applied to an echo canceller for canceling an echo which poses problems on a relatively long line with a transmission path delay accompanied by 2-to-4-wire conversion.
In system identification using an adaptive filter, in order to estimate an output signal y(t) from a system by referring to a signal x(t) input to this system, the coefficient wi(t) of the adaptive filter is updated using a difference e(t)=(y(t)-y(t)) between an output y(t) from the adaptive filter and the output y(t).
More specifically, a conventional method of canceling a reflected signal (echo) generated in 2-to-4-wire conversion serving as a target system will be described by exemplifying a learning identification method used in an echo canceller as a system 25 identification method. This learning identification method is described in, e.g., Noda and Nagumo, "A Learning Method for System Identification", Measurement and Control, Vol. 7, No. 9, pp. 597-605, September, 1968 (reference 1).
Assuming an adaptive FIR filter with N taps, a pseudo echo y(t) as a filter output at time t is calculated from equation (1): ##EQU1## where wi(t) is the ith filter coefficient at time t, and x(t) is the reference signal at time t.
The pseudo echo y(t) in equation (1) is subtracted from the echo signal y(t) at time t to cancel an echo, as given by equation (2): EQU e(t)=y(t)-y(t) (2)
The filter coefficient wi(t) is updated by equation (3) so as to minimize the residual signal e(t) in equation (2): EQU wi(t+1)=wi(t)+.mu.(t)e(t).times.(t-i) (3)
The step size .mu.(t) in equation (3) is given by equation (4): EQU .mu.(t)=.mu.0/PX(t) (4)
where .mu.0 is a positive constant which influences the convergence speed, and PX(t) is the power of the reference signal and given by equation (5): ##EQU2##
As represented by equations (1) to (5), generation of the pseudo echo, calculation of the power of the reference signal, and update of the filter coefficient require the calculation amount proportional to N and memories used by the calculation.
An LMS (Least Mean Square) algorithm such as the learning identification method is known to have a low convergence speed proportional to N (see, e.g., "The LMS Algorithm", Adaptive Signal Processing (part III, "Adaptive Algorithms and Structures"), pp. 99-103, Prentica-Hall, 1985 (reference 2)).
On the other hand, a "responding part" (also referred to as a "waveform responding part") of an impulse response on an echo path is only part of the entire impulse response, as shown in FIG. 8. FIG. 8 shows an example of the impulse response on the echo path by plotting the time on the abscissa and the magnitude on the ordinate.
To cancel an echo, the "responding part" must be estimated using the filter coefficients of the N taps (blocks) of the adaptive filter. In general, however, the location of the "responding part" is unknown, so the largest value is assumed to determine the value N. For this reason, the adaptive filter practically has the filter coefficient of a "fixed delay part" and a filter coefficient subsequent to the "responding part" that converges to "0" (zero). The filter coefficient that converges to "0" need not be processed by equations (1) and (3) and considered.
Wasteful processing can be eliminated by classifying the respective taps into taps (to be referred to as effective taps or blocks hereinafter) for performing calculation associated with the filter, and taps (to be referred to as ineffective taps or blocks hereinafter) for not performing any calculation.
For example, Japanese Patent Laid-Open No. 4-245810 (reference 3) discloses a method in which effective taps are intensively arranged at a "responding part" to increase the convergence speed and decrease the number of memories. That is, reference 3 proposes a system for an adaptive filter in a method and device for estimating system characteristics wherein the convergence time is shortened by changing the rearrangement number of tap locations in assigning the limited number of taps to the actual waveform responding part of an impulse response.
FIG. 6 shows a system characteristic estimating device proposed in reference 3. In FIG. 6, input signals 901 are input parallel as N successive data x(t), . . . , x(t-N+1) to a matrix switch 905 through (N-1) delay elements 909.sub.1 to 909.sub.N. Upon reception of an instruction from a controller 906, the matrix switch 905 connects taps to M (M&lt;N) tap circuits 910.sub.1 to 910.sub.m. Taps connected to tap circuits at this time are called "effective taps", and taps not connected are called "ineffective taps".
The tap circuits 910.sub.1 to 910.sub.M calculate equation (3) using input signals x(t-i) (M signals satisfying 0&lt;i&lt;N-1), an error signal e(t) as an output from a subtracter 904 obtained by subtracting an output y(t) of an adaptive filter 920 from an output y(t) of an unknown system 930 including a hybrid transformer 903, and a constant .mu..
An adder 908 adds outputs from the tap circuits 910.sub.1 to 910.sub.M in accordance with equation (1) to obtain an output from the adaptive filter 920.
In the above-mentioned conventional system, connection of taps to the tap circuits is switched by the matrix switch 905 in units of taps. For this purpose, the controller 906 for controlling switching of the connection by the matrix switch 905, monitors and orders outputs (to be referred to as filter coefficients hereinafter) from the coefficient generators of the tap circuits 910.sub.1 to 910.sub.M.
FIG. 7 shows the arrangement of the controller 906 shown in FIG. 6. The role of the controller 906 is to select effective taps, as described above. In other words, the controller 906 selects a tap to be switched from "effective" to "ineffective" and a tap to be switched from "ineffective" to "effective" in exchanging effective and ineffective taps.
In FIG. 7, a selector 954 selects one signal from M signals 951 input from the tap circuits 910.sub.1 to 910.sub.M. A minimum value monitoring circuit 970 made up of a comparator 956 and a memory circuit 957 determines whether the power of the selected signal is minimum. In the minimum value monitoring circuit 970, the memory 957 stores the minimum value and a corresponding effective tap number. The comparator 956 compares an output from an absolute value circuit 955 for calculating the absolute value of the signal selected by the selector 954 with the minimum value stored in the memory 957 in accordance with the effective tap number.
At the timing of a timing circuit 962, a selector 959 exchanges the effective tap number output from the minimum value monitoring circuit 970 and stored in a FIFO (First-In First-Out) memory 958, and an output from a delay element 960 storing an ineffective tap number. An output from the selector 959 is stored in a memory 961 and used as a control signal for the matrix switch 905.
In realizing the adaptive filter, there are three important subjects, i.e., the hardware scale, the calculation amount, and the convergence speed. The above conventional technique suffers the following problems.
First, the calculation amount is large owing to the following reason. In the conventional technique, selection of "effective" and "ineffective" taps is performed in units of taps, and thus determination processing must be performed within a short time because the filter coefficient greatly varies every estimation calculation.
To compare filter coefficients, processing must be performed for N filter coefficients in a time interval between one estimation calculation and the next estimation calculation. To distribute this processing, a filter coefficient at a certain timing must be stored, or the estimation calculation must be stopped. However, the storage of the filter coefficient leads to a large hardware scale, and the stop of the estimation calculation results in a low convergence speed.
To perform processing without any distribution, it must be performed for M filter coefficients at a sample interval in which a signal is input, and the calculation amount inevitably increases (high-speed processing is required).
Second, the estimation processing is unstable due to the following reason. In the conventional technique, since control is performed in units of taps, a tap is determined to be "ineffective" even at the "responding part" of the impulse response. Stably performing the estimation processing requires complicated processing such as "calculation of the variance".